Fissiamo un linguaggio del prim’ordine \(L\).
Definizione Una formula atomica (nel linguaggio \(L\)) è una stringa della forma \[(R ( t_{1} , \dots , t_{n} ))\] dove \(R\) è un simbolo di predicato \(n\)-ario in \(L\) e \(t_{1}, \dotsc, t_{n}\) sono termini (nel linguaggio \(L\)), oppure della forma \[(t_{1} = t_{2})\] dove \(t_{1} , t_{2}\) sono termini (nel linguaggio \(L\)).
Attenzione! Anche in questo caso le virgole non sono necessarie, ma possono aiutare nella lettura della formula.
Formule atomiche, equazioni e disequazioni Consideriamo il linguaggio \(L = \{ <,+, \cdot , 1, 0 \}\) dove \(<\) è un simbolo di relazione binario, \(+\) e \(\cdot\) sono simboli di funzione binari, e \(1,0\) sono simboli di costante. Abbiamo visto che il termine \(t\) \[+( \cdot(x,x), 1)\] corrisponde (utilizzando la notazione infissa) al polinomio \[x^2+1\]
La formula atomica \[(+( \cdot(x,x), 1)=0)\] eprime allora nel linguaggio \(L\) l’equazione \[x^2+1=0,\]
mentre \[(<(+( \cdot(x,x), 1),0))\] esprime, utilizzando la notazione infissa per \(<\), la disequazione \(x^2+1<0\).
Per riconoscere se una data stringa è una formula atomica, si procede come segue:
Algoritmo per il riconoscimento di formule atomiche
Il primo e l’ultimo simbolo della stringa devono essere una parentesi sinistra e una parentesi destra, rispettivamente.
Se il secondo simbolo della stringa è un simbolo di relazione \(n\)-ario \(R \in L\), allora la formula atomica deve essere del tipo \((R( t_{1}, \dotsc, t_{n}))\), dove \(n = ar(R)\): quindi si controlla che il terzo simbolo sia una parentesi sinistra e il penultimo simbolo sia una parentesi destra, si analizza la stringa compresa tra queste parentesi per individuare i termini \(t_{1}, \dotsc, t_{n}\) (l’algoritmo è lo stesso di quello utilizzato nel caso dei termini), e infine se ne costruisce l’albero sintattico per controllare che siano termini ben formati.
Se il secondo simbolo della stringa è una variabile, una costante o un simbolo di funzione, allora la formula deve essere del tipo \((t_{1} = t_{2})\): si cerca allora il simbolo di uguaglianza (ce ne deve essere solo uno!), si individuano i termini \(t_{1}\) e \(t_{2}\), e se ne costruisce l’albero sintattico per controllare che siano termini ben formati.
Nei restanti casi, la stringa data non era una formula atomica.
Sia \(L = \{ P, f,c \}\) con \(P\) simbolo di relazione binario, \(f\) simbolo di funzione unario e \(c\) simbolo di costante. Verifichiamo se la stringa \[(P(f(x)c))\] è una formula atomica oppure no.
Dall’analisi fatta, risulta che la stringa è del tipo \((P(t_{1}t_{2}))\), dove \(t_{1}\) è \(f(x)\) e \(t_{2}\) è \(c\): poiché questi ultimo sono termini ben formati, la stringa è una formula atomica.Reintroducendo le virgole, tale formula atomica si scrive \[(P(f(x),c)).\]
Sia \(L = \{ P, f,c \}\) con \(P\) simbolo di relazione binario, \(f\) simbolo di funzione unario e \(c\) simbolo di costante. Verifichiamo se la stringa \[( f(f(x))= f(c))\] è una formula atomica oppure no.
Dall’analisi fatta, risulta che la stringa è del tipo \((t_{1} = t_{2})\), dove \(t_{1}\) è \(f(f(x))\) e \(t_{2}\) è \(f(c)\):poiché questi ultimo sono termini ben formati, la stringa è una formula atomica.
Formule del prim’ordine L’insieme delle formule del linguaggio \(L\) (o, più brevemente, \(L\)-formule) è definito ricorsivamente dalle clausole:
una formula atomica è una formula;
se \( \phi \) è una formula, allora anche \(( \neg \phi )\) è una formula,
se \(\phi\) e \(\psi\) sono formule, allora anche \(( \phi \wedge \psi )\), \(( \phi \vee \psi )\), \(( \phi \to \psi )\) e \(( \phi \leftrightarrow \psi )\) sono formule;
se \(\phi\) è una formula e \(x\) è una variabile, allora anche \((\exists x \phi)\) e \((\forall x \phi)\) sono formule. In questo caso, \(\phi\) viene detta raggio d’azione del quantificatore \(\exists x\) o \(\forall x\).
Useremo le lettere greche \(\phi\), \(\psi\), e \(\chi\), variamente decorate, per le formule.
Tecnicamente, bisognerebbe di nuovo dare una definizione per ricorsione degli insiemi \(\mathsf{Fml}_{n}\) per \(n\in \mathbb{N}\): \(\mathsf{Fml}_{0}\) è l’insieme delle formule atomiche e \(\mathsf{Fml}_{n+1}\) è l’unione di \(\mathsf{Fml}_{n}\) con l’insieme delle formule che si ottengono applicando una delle regole qui sopra a formule in \(\mathsf{Fml}_{n}\). L’insieme delle formule è allora \(\mathsf{Fml} = \bigcup_{n \in \mathbb{N}} \mathsf{Fml}_{n}\). L’altezza \(ht(\phi)\) di una formula \(\phi \in \mathsf{Fml}\) è definita nella maniera usuale.
La costante logica principale di una \(L\)-formula (non atomica) \(\phi\) è l’ultima costante logica introdotta per creare \(\phi\) in accordo con la definizione ricorsiva data. Più precisamente:
se \(\phi\) è della forma \((\neg\psi)\), allora \(\neg\) è la costante logica principale di \(\phi\), mentre \(\psi\) viene detta sottoformula principale di \(\phi\);
se \(\phi\) è della forma \((\psi\mathrel{\Box} \chi)\), dove \(\Box\) è uno dei connettivi binari \(\wedge\), \(\vee\), \(\rightarrow\), \(\leftrightarrow\), allora \(\Box\) è la costante logica principale di \(\phi\), mentre \(\psi\) e \(\chi\) sono le sottoformule principali di \(\phi\);
infine, se \(\phi\) è della forma \((\exists x \psi)\) oppure della forma \((\forall x \psi)\), allora \(\exists\) e \(\forall\) sono, rispettivamente, la costante logica principale di \(\phi\), mentre \(\psi\) viene detta sottoformula principale di \(\phi\).
Nei casi
1 e 2parliamo anche di connettivo principale di \(\phi\), nel caso
3parliamo invece di quantificatore principale di \(\phi\).
Diciamo che una formula \(\phi\) è una negazione, congiunzione, disgiunzione, implicazione, bi-implicazione, formula esistenziale oppure formula universale quando la sua costante logica principale è \(\neg\), \(\wedge\), \(\vee\), \(\rightarrow\), \(\leftrightarrow\), \(\exists\) o \(\forall\), rispettivamente.
Per individuare la costante logica principale di una \(L\)-formula \(\phi\) si usa (l’ovvia variante del)l’algoritmo visto per la logica proposizionale.
Il primo e l’ultimo simbolo della stringa devono essere una parentesi sinistra e una parentesi destra, rispettivamente. Consideriamo il secondo simbolo della stringa.
Se il secondo simbolo è \(\neg\) oppure una parentesi sinistra \((\), allora si procede come visto per la logica proposizionale: nel primo caso la costante logica principale è proprio \(\neg\), mentre nel secondo caso la costante logica principale è uno dei connettivi binari \(\wedge\), \(\vee\), \(\rightarrow\), \(\leftrightarrow\), e precisamente quello che segue la parentesi destra che chiude la parentesi sinistra in esame.
Altrimenti, il secondo simbolo è \(\exists\) oppure \(\forall\): in questo caso, tale quantificatore è proprio la costante logica principale di \(\phi\). Esso dovrà necessariamente essere seguito da una variabile, e ciò che segue tale variabile (esclusa l’ultima parentesi di chiusura) è la sottoformula principale di \(\phi\).
Albero sintattico di una formula
Si etichetta la radice con la formula data.
Sia \(\phi\) la formula che compare nell’etichetta di un nodo:
se \(\phi\) è una formula atomica (ben formata) non si aggiunge alcun successore al nodo, che diventerà una foglia dell’albero;
se \(\phi\) è una negazione, ovvero è del tipo \((\neg \psi )\), si aggiunge un solo successore al nodo e lo si etichetta con \(\psi\);
se la costante logica principale di \(\phi\) è un connettivo binario \(\Box \in \{ \wedge, \vee, \rightarrow, \leftrightarrow \}\), ovvero \(\phi\) è del tipo \((\psi \mathrel{\Box} \chi)\) con \(\Box\) connettivo binario, allora si aggiungono due successori al nodo etichettandoli con \(\psi\) e \(\chi\), rispettivamente;
se la costante logica principale di \(\phi\) è un quantificatore, ovvero \(\phi\) è del tipo \((\exists x \psi )\) oppure \((\forall x \psi)\), allora si aggiunge un solo successore al nodo etichettandolo con \(\psi\).
L’albero sintattico di \( (\exists x ((\neg (R(x,c))) \wedge ((P(x)) \to (f(x) = c)))) \) è
Le formula che compaiono nei nodi dell’albero sintattico si chiamano sottoformule della formula data.
Anche per le formule del prim’ordine vale la regola che l’altezza della formula è uguale all’altezza dell’albero diminuita di una unità.
L’albero sintattico in forma compatta dello stesso termine: \[(\exists x ((\neg (R(x,c))) \wedge ((P(x)) \to (f(x) = c))))\] è
Le formula che compaiono nei nodi dell’albero sintattico si chiamano sottoformule della formula data.
Anche per le formule del prim’ordine vale la regola che l’altezza della formula è uguale all’altezza dell’albero diminuita di una unità.
Calcolare l’albero sintattico della formula \[((\exists x (\forall y ( (P ( x , y )) \to (Q ( x )) ) ) )\to ((\forall z (R ( z ))) \vee (S ( z )))) .\]
Soluzione: